package cn.leonis.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author Tobi
 * @date 2021-06-07 8:58
 * 找出两个链表的相交的节点
 */
public class IntersectionNodeSolution {

    public static void main(String[] args) {
        List<ListNode> listA = new ArrayList<>();
        listA.add(new ListNode(1));
        listA.add(new ListNode(3));
        listA.add(new ListNode(5));
        listA.add(new ListNode(7));

        List<ListNode> listB = new ArrayList<>();
        listB.add(new ListNode(5));
        listB.add(new ListNode(7));

        IntersectionNodeSolution solution = new IntersectionNodeSolution();

        // 错误的测试用例
        System.out.println(solution.getIntersectionNode(listA.get(0), listB.get(0)));
    }


    /**
     * 第一种解法：使用Hash集合来存储遍历链表headA的值，然后遍历headB，在Hash集合里面寻找值
     * 这种解法需要遍历两个链表，因此时间复杂度为O(m + n) , 空间复杂度为 O(m)
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> hashSet = new HashSet<>();

        ListNode temp = headA;

        // 从headA开始，循环遍历链表A，并且将其存入hashset中
        while (temp != null) {
            hashSet.add(temp);
            temp = temp.next;
        }

        temp = headB;

        while (temp != null) {
            if (hashSet.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }

        return null;

    }

    /**
     * 第二种解法：使用双指针，一个指针遍历链表A，一个指针遍历链表B，如果第一个指针遍历完成了A，则指向B的开头开始遍历；遍历B的指针完成后，则指向A的开头遍历
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA, pB = headB;

        // 要么是返回相交的点，要么是不相交，返回最后的空节点
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }

        return pA;

    }
}
